public class PostInOrder_0316 {
    /*
    给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
     */
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    private int getpos (int k, int[] inorder, int inBegin, int inEnd) {
        for (int i = inBegin; i <= inEnd; i++) {
            if (inorder[i] == k) return i;
        }
        return -1;
    }
    private int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1;
        return buildTreeChild(inorder, 0, inorder.length - 1, postorder);
    }
    private TreeNode buildTreeChild (int[] inorder, int inBegin, int inEnd, int[]postorder) {
        if (inBegin > inEnd) return null;
        TreeNode root = new TreeNode(postorder[postIndex]);
        int pos = getpos(postorder[postIndex],inorder,inBegin,inEnd);
        if (pos == -1) return null;
        postIndex--;
        root.right = buildTreeChild(inorder,pos + 1,inEnd, postorder);
        root.left = buildTreeChild(inorder,inBegin,pos - 1, postorder);

        return root;
    }
}
